package java;

import java.util.Arrays;

public class Question31 {
    public static void main(String[] args) {
        int[] arr = {1,2,3};
        nextPermutation(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void nextPermutation(int[] nums) {
        if (nums == null || nums.length < 1) {
            return;
        }
        int right = nums.length - 1;
        int left = -1;
        int exchangeRight = right;
        while (right > 0){
            if (left < right){
                for (int i = left + 1; i <= right;i ++){
                    if (nums[i] < nums[right]){
                        exchangeRight = right;
                        left = i;
                    }
                }
            }
            right --;
        }
        if (left != -1){
            int temp = nums[exchangeRight];
            nums[exchangeRight] = nums[left];
            nums[left] = temp;
            sortRight(nums,left);
            return;
        }

        sortRight(nums,-1);
    }

    private static void sortRight(int[] nums, int start) {
        int index = start + 1;
        while (index < nums.length){
            int right = nums.length - 1;
            while (index < right){
                if (nums[right] < nums[right - 1]){
                    int temp = nums[right];
                    nums[right] = nums[right - 1];
                    nums[right - 1] = temp;
                }
                right --;
            }
            index ++;
        }
    }
}
